package org.example.algo;

/**
 * 用单链表实现队列
 * @author shenguangyang
 */
public class N07_SingleLinkedForQueueAndStack {
    public static void main(String[] args) {
        System.out.println("=========================================== 用单链表实现队列");
        MyQueue<Integer> myQueue = new MyQueue<>();
        myQueue.offer(7);
        myQueue.offer(2);
        myQueue.offer(3);
        myQueue.offer(4);
        myQueue.printf();

        System.out.println("======================>poll");
        for (int i = 0; i < 5; i++) {
            System.out.println(myQueue.poll());
        }

        myQueue.printf();

        System.out.println("=========================================== 用单链表实现栈");
        MyStack<Integer> myStack = new MyStack<>();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.printf();
        System.out.println("======================>pop");
        for (int i = 0; i < 4; i++) {
            System.out.println(myStack.pop());
        }
    }

    public static class Node<V> {
        V value;
        Node<V> next;

        public Node(V value) {
            this.value = value;
        }
    }

    /**
     * 队列
     * @param <V>
     */
    public static class MyQueue<V> {
        Node<V> head;
        Node<V> tail;
        int size;

        public MyQueue() {
        }

        public int size() {
            return size;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        /**
         * 添加元素
         * 添加到尾部
         */
        public void offer(V v) {
            if (v == null) {
                return;
            }
            Node<V> node = new Node<>(v);
            if (tail == null) {
                head = node;
            } else {
                tail.next = node;
            }
            tail = node;
            size++;
        }

        public V poll() {
            V result;
            if (isEmpty()) {
                return null;
            }
            result = head.value;
            head = head.next;
            if (head == null) {
                tail = null;
            }
            size--;
            return result;
        }

        /**
         * 拿到值, 不弹出
         */
        public V peek() {
            V result;
            if (isEmpty()) {
                return null;
            }
            result = head.value;
            return result;
        }

        public void printf() {
            if (head == null) {
                return;
            }
            System.out.println("printf ========== start, size: " + size);
            Node<V> cur = head;
            while (cur != null) {
                System.out.println(cur.value);
                cur = cur.next;
            }
            System.out.println("printf ========== end\n");
        }
    }

    /**
     * 栈
     */
    public static class MyStack<V> {
        Node<V> head;
        int size;

        public MyStack() {
        }

        public void push(V v) {
            Node<V> newNode = new Node<>(v);
            if (head == null) {
                head = newNode;
            } else {
                newNode.next = head;
                head = newNode;

            }
            size++;
        }

        public V pop() {
            if (head == null || size == 0) {
                return null;
            }
            V result = head.value;
            head = head.next;
            size--;
            return result;
        }

        public V peek() {
            if (head == null || size == 0) {
                return null;
            }
            Node<V> result = head.next;
            return result.value;
        }

        public void printf() {
            if (head == null) {
                return;
            }
            System.out.println("printf ========== start, size: " + size);
            Node<V> cur = head;
            while (cur != null) {
                System.out.println(cur.value);
                cur = cur.next;
            }
            System.out.println("printf ========== end\n");
        }
    }
}
